一、TSP问题

TSP问题（Travelling Salesman Problem）即旅行商问题，又译为旅行推销员问题、货郎担问题，是数学领域中著名问题之一。假设有一个旅行商人要拜访n个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。TSP问题可以分为两类，一类是对称TSP问题（Symmetric TSP），另一类是非对称问题（Asymmetric TSP）。所有的TSP问题都可以用一个图（Graph）来描述：

V={c1, c2, …, ci, …, cn}，i = 1,2, …, n，是所有城市的集合.ci表示第i个城市，n为城市的数目；

E={(r, s): r,s∈ V}是所有城市之间连接的集合；

C = {crs: r,s∈ V}是所有城市之间连接的成本度量（一般为城市之间的距离）；

如果crs = csr, 那么该TSP问题为对称的，否则为非对称的。

一个TSP问题可以表达为：

求解遍历图G = (V, E, C)，所有的节点一次并且回到起始节点，使得连接这些节点的路径成本最低。

二、遗传算法

遗传算法（Genetic Algorithms ）是基于生物进化理论的原理发展起来的一种广为应用的、高效的随机搜索与优化的方法。其主要特点是群体搜索策略和群体中个体之间的信息交换，搜索不依赖于梯度信息。它是在70年代初期由美国密西根（ Michigan ）大学的霍兰（ Holland ）教授发展起来的。1975年霍兰教授发表了第一本比较系统论述遗传算法的专著《自然系统与人工系统中的适应性》（《 Adaptationin Natural and Artificial Systems 》）。遗传算法最初被研究的出发点不是为专门解决最优化问题而设计的，它与进化策略、进化规划共同构成了进化算法的主要框架，都是为当时人工智能的发展服务的。迄今为止，遗传算法是进化算法中最广为人知的算法。

 遗传火算法的实施步骤如下（以目标函数求最小为例）。     第一步：初始化 t←0进化代数计数器；T是最大进化代数；随机生成M个个体作为初始群体P（t）；     第二步：个体评价 计算P（t）中各个个体的适应度；     第三步：选择运算 将选择算子作用于群体；     第四步：交叉运算 将交叉算子作用于群体；     第五步：变异运算 将变异算子作用于群体，并通过以上运算得到下一代群体P（t + 1）;     第六步：终止条件判断  t≦T：t← t+1 转到步骤2；t>T：终止 输出解。

遗传算法应用步骤：     1）确定决策变量及各种约束条件，即个体的表现型X和问题的解空间；     2）建立优化模型 （目标函数最大OR 最小） 数学描述形式 量化方法；     3）染色体编码方法；     4）解码方法；     5）个体适应度的量化评价方法 F(x)     6）设计遗传算子；     7）确定有关运行参数。

三、遗传算法求解TSP问题

其实之前不大想写这个遗传算法求TSP，因为我之前已经有遗传算法求01背包了，但有些读者建议，加上确实tsp与01背包差别还是很大的，就再写一个。对于TSP之类的问题NP问题，使用启发式搜索算法是一个明智的选择，因为精确算发已经力不从心了。

使用遗传算法第一件事情就是确定染色编码方式，它根据不同的问题模型使用不同编码方式，有二进制编码也有整数编码和浮点数编码，面对TSP问题，我肯定选用整数编码，因为很简单，对于每个城市用一个整数来编号，例如有48个城市，就用0到47来标识每一个城市，然后一个路径就是一条染色体编码，染色体长度为48，如：0,1,2,3,4...47就是一个染色体，它表达的意思就是旅行者从0号城市出发，依次访问1,2,...47号城市再回到0号城市；遗传算法的第二个要点就是评价函数，TSP的评价函数很简单，就是染色体编码表达的路径总长度；最后很简单，其实在这个模型中就是将0到47这48个数进行全排列，从中找出最短的一条路径（想想48个数全排列，然后比较。。。）。清楚了解了这些，咱们就可以按照上面的遗传算法框架来进行编程了。

我们使用TSP问题依然来自于tsplib上的数据att48，这是一个对称TSP问题，城市规模为48，其最优值为10628.其距离计算方法下图所示：

具体代码如下：